package com.dyz.leetcode;

public class CanJump55 {
    //贪心算法
    public boolean canJump(int[] nums) {
        int  max_i = 0;

        for(int i=0; i<nums.length;i++){
            if(i>max_i){return false;}

            int cur_max = i+nums[i];
            max_i = Math.max(cur_max, max_i);
        }
        return max_i>=nums.length-1;
    }
    //动态规划
    public boolean canJump1(int[] nums) {
        int n = nums.length;
        int max_len = 0;
        for (int i=0;  i<n && i<=max_len;i++){
            max_len = Math.max(max_len, i+nums[i]);
            if(max_len>=n-1){
                return true;
            }
        }
        return false;
    }
}
